package jiaoheng.数据结构;

import lombok.Data;

public class s7AVL树 {
    public static void main(String[] args) {

    }

    // 中序遍历
    public void middleSort(TreeNode treeNode){
        if(treeNode.getLeft()!=null){
            middleSort(treeNode.getLeft());
        }
        System.out.println(treeNode.getValue()+" ");
        if(treeNode.getRight()!=null){
            middleSort(treeNode.getRight());
        }
    }
}
@Data
class AVLTree{
    private AVLTreeNode root;



    public void addNode(AVLTreeNode parentNode,AVLTreeNode newNode){
        // 普通bst树的插入
        if(parentNode==null){
            this.setRoot(newNode);
        }
        if(newNode.getValue()<parentNode.getValue()){
            if(parentNode.getLeft()==null){
                parentNode.setLeft(newNode);
            }else{
                addNode(parentNode.getLeft(),newNode);
            }
        }else{
            if(parentNode.getRight()==null){
                parentNode.setRight(newNode);
            }else{
                addNode(parentNode.getRight(),newNode);
            }
        }
        // 更新父节点的高度，这个节点的高度不一定会增加
        parentNode.setHeight(Math.max(parentNode.getLeft()==null?0:parentNode.getLeft().getHeight(),parentNode.getRight()==null?0:parentNode.getRight().getHeight()));
        // 获取平衡因子(左节点高度-右节点高度)
        // 写不下去了，旋转逻辑多
    }

    public void height(AVLTreeNode treeNode){

    }

    public void middleSort(AVLTreeNode treeNode){
        if(treeNode.getLeft()!=null){
            middleSort(treeNode.getLeft());
        }
        System.out.println(treeNode.getValue()+" ");
        if(treeNode.getRight()!=null){
            middleSort(treeNode.getRight());
        }
    }

}

@Data
class AVLTreeNode{
    private int value;
    private int height = 1; // 这里设置成1是为了获取空node的高度时返回高度为0
    private AVLTreeNode left;
    private AVLTreeNode right;

    public AVLTreeNode(int value){
        this.value=value;
    }


}
